A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between stations, such as computers. A local area network (LAN) is an example of such a subnetwork consisting of a transmission medium, such as coaxial cable or twisted pair, that provides relatively short distance communication among interconnected stations. A plurality of LANs may be further interconnected by an intermediate station, called a bridge, to extend the effective "size" of the computer network and increase the number of communicating stations. The stations typically communicate by exchanging discrete packets or "frames" of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the stations interact with each other.
Most networks are typically organized as a series of hardware and software levels or "layers" within each station. These layers interact to format data for transfer between, e.g., a source station and a destination station communicating over the network. Specifically, predetermined services are performed on the data as it passes through each layer and the layers communicate with each other by means of the predefined protocols. This layered design permits each layer to offer selected services to other layers using a standardized interface that shields those layers from the details of actual implementation of the services.
In an attempt to standardize network architectures, i.e., the sets of layers and protocols used within a network, a generalized model has been proposed by the International Standards Organization (ISO). The model, called the Open Systems Interconnection (OSI) reference model, is directed to the interconnection of systems that are "open" for communication with other systems. The proposed OSI model has seven layers which are termed, in ascending interfacing order, the physical, data link, network, transport, session, presentation, and application layers. These layers are arranged to form a "protocol stack" in each station of the network.
FIG. 1 illustrates a schematic block diagram of prior art protocol stacks 125 and 175 used to transmit data between a source station 110 and a destination station 150, respectively, of a LAN 100. Each protocol stack comprises a collection of protocols, one per layer, and is preferably structured according to the OSI seven-layer model. As can be seen, the protocol stacks 125 and 175 are physically connected through a communications channel 180 at the physical layers 124 and 164. For ease of description, the protocol stack 125 will be described.
In general, the application layer 112 contains a variety of protocol functions that are commonly needed by software processes, e.g., sending process 104, executing on the station, while the presentation layer 114 is responsible for the presentation of transmitted data in a meaningful manner to the application layer. The session layer 116, transport layer 118 and network layer 120 are substantially involved in implementing different forms of connectivity from the source station to the destination station.
IEEE project 802 defines a flexible network architecture oriented to the implementation of LANs. Although it generally conforms with the OSI model, the IEEE approach addresses only the lowest two layers of that model, the physical and data link layers. Specifically, the physical layer 124 is concerned with the actual transmission of signals across the communication channel; in this context, the physical layer defines the types of cabling, plugs and connectors used in connection with the channel.
The data link layer 122, on the other hand, is responsible for transmission of data from one station to another. In the IEEE 802 architecture, the data link layer is divided into two sublayers: logical link control (LLC) and media access control (MAC). The LLC sublayer 180 allows the overlying network layer to access the services of the LAN without regard to the actual network implementation; more specifically, the LLC layer initiates control signal interchange, organizes data flow, interprets commands and generates responses.
The MAC sublayer 182 is primarily concerned with the controlling access to the transmission medium and, to that end, defines rules or procedures by which the stations must abide in order to share the medium. The MAC layer further provides addressing and framing functions, the latter including the addition of header and trailer information needed to identify the boundaries of frames, to synchronize communication between source and destination stations, and to route the frames.
Data transmission over the LAN 100 therefore consists of generating data in, e.g., sending process 104 executing on the source station 110, passing that data to the application layer 112 and down through the layers of the protocol stack 125, where the data are sequentially formatted as a frame for delivery onto the channel 180 as bits. Those frame bits are then transmitted to the protocol stack 175 of the destination station 150, where they are passed up that stack to a receiving process 174. Data flow is schematically illustrated by solid arrows.
Although actual data transmission occurs vertically through the stacks, each layer is programmed as though such transmission were horizontal. That is, each layer in the source station 100 is programmed to transmit data to its corresponding layer in the destination station 150, as schematically shown by dotted arrows. To achieve this effect, each layer of the protocol stack 125 in the source station 110 typically adds information (in the form of a header field) to the data frame generated by the sending process as the frame descends the stack. At the destination station 150, the various headers are stripped off one-by-one as the frame propagates up the layers of stack 175 until it arrives at the receiving process.
Access to the LAN is typically shared among the stations in accordance with various access control methods depending upon the topology of the subnetwork and the type of transmission control employed. A popular subnetwork topology is a ring network that is typically formed by configuring the communication channel as a loop and coupling the stations at intervals around the loop. The stations communicate by transmitting and receiving discrete signals in the form of data frames according to predefined protocols. Acceptance of a frame by each station, in turn, is determined on the basis of an address contained in the frame.
With LANs that employ a ring topology, a commonly used access control method is token passing. Token passing is a form of distributed transmission control wherein all the stations on the subnetwork cooperate in controlling access to the communication channel. Here, a small message or token is passed from one station to the next along the ring. If the token is marked as free, the station receiving it can transmit a message over the ring. A token ring network is an example of a ring topology that uses token passing as an access control method.
Token ring networks may be further interconnected using a bridge whose primary function is to transfer frames between the rings. A route is the path a frame travels through the subnetworks from a source station to a destination station. Depending upon how the rings are interconnected, there may be more than one possible path for a frame to follow. Once the source station has "discovered" an optimal path to the destination, it transmits specifically-routed frames over the subnetworks; as the name implies, these frames include information specifying the route to, along with the address of, the destination station.
Source-Route-Bridge (SRB) is a source routing technique used by a source station to discover the optimal path to a destination. According to this networking technique, the source station specifies the optimal route, which is determined in accordance with routing information acquired from the stations of the network. A special type of frame, called an explorer frame, is typically used by the source to collect and store that information in a routing information (RI) field of the frame.
In one embodiment of SRB networking, the source station issues a broadcast explorer frame that is received by each station on the local ring subnetwork. Here, the source is unaware of the MAC address of the destination station and the path (or paths) for reaching that station, so it issues the explorer frame having a broadcast address that all stations are configured to receive. Each bridge copies the frame and supplies information relating to the route (i.e., bridge and ring numbers) within the RI field; it then distributes the copy to all stations on its interconnected ring. Eventually, a copy of the broadcast explorer frame reaches every station on every LAN of the network. Each station may respond to the source by issuing a response frame containing its MAC address and the routing information. The source station can examine the routes followed by the explorer frames and choose the best path for the particular destination.
In another embodiment, the source creates a unicast explorer frame that includes the MAC address of the destination station. The frame is transmitted over the source's local ring subnetwork, where it is received by bridges connecting the local ring to other ring subnetworks. As the unicast explorer frame passes over these interconnected rings, routing information is again stored in the RI field by the bridges. If there is more than one route, more than one frame will eventually reach the destination, with each frame containing different routing information.
In response to each received explorer frame, the destination station returns a response frame containing the routing information for each possible route. The source station examines the information contained in these response frames and selects an optimal path to the destination based on that information; it then may communicate with the destination by sending data frames over that selected path.
A disadvantage of the conventional explorer techniques involves the exponential overhead of bandwidth that is consumed every time a source station attempts to discover an optimal path to a destination. That is, transmission of the explorer frames consumes a significant amount of bandwidth because copies of those frames are created and distributed by bridges connecting the source station to all possible paths leading to the destination station. In addition, the response frames returned by the destination consume an appreciable amount of network bandwidth.
Moreover, SRB networking constrains the ability of a network administrator to set certain policy decisions for the network, such as cost and load balancing. In other words, because the dispositive routing information is provided by the explorer response frame, the network administrator effectively has no control over the determination of a communication path between the source and destination stations.